#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//typedef int BTDataType;
typedef struct BTNode {
    int val;
    struct BTNode* left;
    struct BTNode* right;
    
}BTNode;

BTNode* BuyNode(int x)
 {
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
     root->val = x;
     root->left = NULL;
     root->right = NULL;
     return root;
 }

BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyNode(2);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(2);
    BTNode* node4 = BuyNode(5);
    BTNode* node5 = BuyNode(2);
    node1->left = node2;
    node1->right = node3;
    node2->left = node3;
    node2->right = node4;
    node3->right = node5;
    return node1;
}


 //int BTreeSize(struct TreeNode* root)
 //{
 //    return root == NULL ? 0 : 1 + BTreeSize(root->left) + BTreeSize(root->right);
 //}

 //void _preorderTraversal(struct TreeNode* root, int* arr, int* pi)
 //{
 //    if (root == NULL)
 //        return;
 //    arr[(*pi)++] = root->val;
 //    _preorderTraversal(root->left, arr, pi);
 //    _preorderTraversal(root->right, arr, pi);
 //}

 //int* preorderTraversal(struct TreeNode* root, int* returnSize) {
 //    *returnSize = BTreeSize(root);
 //    int* Retarrry = (int*)malloc(*returnSize * sizeof(int));
 //    int i = 0;
 //    _preorderTraversal(root, Retarrry, &i);
 //    return Retarrry;
 //}



//int BTreeSize(struct TreeNode* root)
//{
//    if (root == NULL)
//        return 0;
//    return 1 + BTreeSize(root->left) + BTreeSize(root->right);
//}
//
//void _inorderTraversal(struct TreeNode* root, int* arr, int* pi)
//{
//    if (root == NULL)
//        return;
//    _inorderTraversal(root->left, arr, pi);
//    arr[(*pi)++] = root->val;
//    _inorderTraversal(root->right, arr, pi);
//}
//
//int* inorderTraversal(struct TreeNode* root, int* returnSize) {
//    *returnSize = BTreeSize(root);
//    int* RetArray = (int*)malloc(*returnSize * sizeof(int));
//    int i = 0;
//    _inorderTraversal(root, RetArray, &i);
//    return RetArray;
//}




//int BinaryTreeLeafSize(BTNode* root)
//{
//    if (root == NULL)
//        return 0;
//    if (root->left == NULL && root->right == NULL)
//        return 1;
//    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
//}


//int BinaryTreeLevelKSize(BTNode* root, int k)
//{
//    assert(k > 0);
//    if (root == NULL)
//        return 0;
//    if (k == 1)
//        return 1;
//    return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
//}

//
//BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
//{
//    if (root == NULL)
//        return NULL;
//    if (root->val == x)
//        return root;
//    BTNode* leftRoot = root->left;
//    if (leftRoot)
//        BinaryTreeFind(leftRoot,x);
//    BinaryTreeFind(root->right, x);
//}


//int BinaryTreeHeight(BTNode* root)
//{
//    if (root == NULL)
//        return 0;
//    int LeftHeight = BinaryTreeHeight(root->left);
//    int RightHeight = BinaryTreeHeight(root->right);
//    return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
//}


//bool isUnivalTree(struct TreeNode* root) {
//    if (root == NULL)
//        return true;
//    if ((root->left && root->left->val != root->val)
//        || (root->right && root->right->val != root->val))
//        return false;
//    return isUnivalTree(root->left) && isUnivalTree(root->right);
//}


